import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

//满二叉树，满二叉树是一种特殊的二叉树
//完全二叉树，从上到下，从左到右一次排列
/*
性质：
1，若规定根节点的层数为1，则一颗非空二叉树的第i层上最多有2^i-1个节点
2， 如规定根结点的二叉树的深度为为1，则深度为k的二叉树的最大节点数是2^-1
3，对任意一颗二叉树，如果其叶节点的个数为n0，度为2的非叶节点个数为n2，则有n0=n2+1
4,具有n个节点的完全二叉树的深度为log2（n+1）上取整
5，对于具有n个节点的完全二叉树，如果按照从上至下从左至右所有节点从0开始编号，如果父节点的下标为i，则
如果2i+1<n,左孩子是序号为2i+1，否则无左孩子，若2i+2<n，右孩子序号为2i+2，否则没有右孩子
6，知道孩子的下标，父节点的下标为（i-1）/2,如果i=0，则无则无双亲节点
 */
class BinaryTree{
    public TreeNode root;
    static class TreeNode{
        public char val;
        public TreeNode left;
        public TreeNode right;
        public  TreeNode (char val){
            this.val=val;
        }
    }
    public TreeNode createTree(){
        TreeNode A=new TreeNode('A');
        TreeNode B=new TreeNode('B');
        TreeNode C=new TreeNode('C');
        TreeNode D=new TreeNode('D');
        TreeNode E=new TreeNode('E');
        TreeNode F=new TreeNode('F');
        TreeNode G=new TreeNode('G');
        TreeNode H=new TreeNode('H');
        A.left=B;
        A.right=C;
        B.left= D;
        B.right=E;
        C.left=F;
        C.right=G;
        E.right=H;
        root=A;
        return root;
    }
/*
前序遍历：根左右
中序遍历：左根右
后序遍历：左右根
(根的位置)
层序遍历
 */
    public void preOrder(TreeNode root){
        if(root==null){
            return;
        }
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);

    }
    public void midOrder(TreeNode root){
        if(root==null){
            return;
        }
        midOrder(root.left);
        System.out.print(root.val+" ");
        midOrder(root.right);

    }
    public void postOrder(TreeNode root){
        if(root==null){
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+" ");

    }
    //一棵树的节点个数
    public int size(TreeNode root){
        if(root==null){
            return 0;
        }
        return size(root.left)+size(root.right)+1;
    }
    public static int nodeSize;
    public void size2(TreeNode root){
        if(root==null){
            return ;
        }
       nodeSize++;
        size2(root.left);
        size2(root.right);
    }
    //求叶子节点的个数
    public int getLeafNodeCount(TreeNode root){
        if(root==null){
            return 0;
        }
        if (root.left==null&&root.right==null){
            return 1;
        }
        return getLeafNodeCount(root.right)+getLeafNodeCount(root.left);
    }

    public static int nodeLeafSize;
    public void getLeafNodeCount2(TreeNode root){
        if(root==null){
            return;
        }
        if (root.left==null&&root.right==null){
            nodeLeafSize++;
            return;
        }
        getLeafNodeCount2(root.left);
        getLeafNodeCount2(root.right);
    }
    //获取k层节点的个数
    //前提k是合法的
    public int getKLevelNodeCount(TreeNode root,int k){
        if(root==null){
            return 0;
        }
        if(k==1){
            return 1;
        }
        return getKLevelNodeCount(root.left,k-1)
                +getKLevelNodeCount(root.right,k-1);

    }
    //获取树的高度(左树和右树的的最大值+1)
    //时间复杂度为O（n）
    public int getHeight(TreeNode root){
        if(root==null){
            return 0;
        }
        int left=getHeight(root.left);
        int right=getHeight(root.right);
        return Math.max(left,right)+1;
    }
    public TreeNode find(TreeNode root,char val){
        if (root==null){
            return null;
        }
        if(root.val==val){
            return root;
        }
        TreeNode ret=find(root.left,val);
        if (ret!=null){
            return ret;
        }
        ret=find(root.right,val);
        if (ret!=null){
            return ret;
        }
        return null;
    }
    //检查两棵树是否相同

    /**
     * 时间复杂度：O(min（m,n）)
     * @param p 有m个节点
     * @param q 有n个节点
     */
    public boolean isSameTree(TreeNode p,TreeNode q){
        //一个为空，一个不为空
        if (q!=null&&p==null||q==null&&p!=null){
            return false;
        }
        if (p==null&&q==null){
            return true;
        }
        if (p.val!=q.val){
            return false;
        }
        return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }
    //第二棵树是否是第一棵树的子树

    /**
     * 时间复杂度：O（m*n）
     * @param root 有n个节点
     * @param subRoot 有m个节点
     */
    public boolean isSubTree(TreeNode root,TreeNode subRoot){
        if (root==null){
            return false;
        }
        if (isSameTree(root,subRoot)){
            return true;
        }
        if (isSubTree(root.left,subRoot)){
            return true;
        }
        if (isSubTree(root.right,subRoot)){
            return true;
        }
        return false;
    }
    private void swap(TreeNode root){
        TreeNode tmp=root.left;
        root.left=root.right;
        root.right=tmp;

    }
    //翻转二叉树
    public TreeNode reverseTree(TreeNode root){
        if (root==null){
            return null;
        }
        if (root.left==null&&root.right==null){
            return root;
        }
        swap(root);
        reverseTree(root.left);
        reverseTree(root.right);
        return root;
    }
    //判断一棵二叉树是否是平衡二叉树（所有节点的高度差小于等于一）

    /**
     * 时间复杂度：0（n*n）
     * @param root
     * @return
     */
    public boolean isBalanced(TreeNode root){
        if (root==null){
            return true;
        }
        int leftH=getHeight(root.left);
        int rightH=getHeight(root.right);
        return Math.abs(leftH-rightH)<=1
                &&isBalanced(root.left)
                &&isBalanced(root.right);
    }
    //优化：
    /**
     * 时间复杂度：0（n）
     * @param root
     * @return
     */
    private int getHeight2(TreeNode root){
        if(root==null){
            return 0;
        }
        int left=getHeight2(root.left);
        if (left<0){
            return -1;
        }
        int right=getHeight2(root.right);
        if (right<0){
            return -1;
        }
        if (Math.abs(left-right)<=1){
            return Math.max(left,right)+1;
        }else {
            return -1;
        }

    }
    public boolean isBalanced2(TreeNode root){
        if (root==null){
            return true;
        }
        //=================================================================================

        return getHeight2(root)<=1;
    }
         //=================================================================================
    //对称二叉树
    public boolean isSymmetric(TreeNode root){
        if (root==null){
            return true;
        }
        return isSymmetricChild(root.left,root.right);


    }
    private boolean isSymmetricChild(TreeNode p,TreeNode q){
        //1，检查结构是否相同-》两个均为空
        if (p==null&&q==null){
            return true;
        }
        //2，检查结构是否相同——》一个为空一个不为空
        if (p!=null&&q==null||p==null&&q!=null){
            return false;
        }
        //3，两个都不为空，判断值是否一样
        if (p.val!=q.val){
            return false;
        }
        //4，判断左树的左是否等于右树的右，右树的左是否等于左树的右
        return isSymmetricChild(p.left,q.right)
                &&isSymmetricChild(p.right,q.left);
    }
    //输入前序遍历（标明了空节点的位置）输出中序遍历
    public int i=0;
    public TreeNode createTree2(String str){
        TreeNode root=null;
        if (str.charAt(i)!='#'){
            root=new TreeNode(str.charAt(i));
            i++;
            root.left=createTree2(str);
            root.right=createTree2(str);
        }else {
            i++;
        }
        return root;
    }
    //层序遍历
    public void levelOrder(TreeNode root){
        Queue<TreeNode> queue=new LinkedList<>();
        if (root==null){
            return;
        }
        queue.offer(root);
        TreeNode cur=null;
        while (!queue.isEmpty()){
            cur=queue.poll();
            System.out.print(cur.val+" ");
            if (cur.left!=null) {
                queue.offer(cur.left);
            }if (cur.right!=null){
                queue.offer(cur.right);
            }
        }
        System.out.println();
    }
    public List<List<Character>> levelOrder2(TreeNode root){
        List<List<Character>> ret=new LinkedList<>();
        if (root==null){
            return ret;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            int size= queue.size();
            List<Character> list=new LinkedList<>();
            while (size>0){
                TreeNode cur=queue.poll();
                list.add(cur.val);
                if (cur.left!=null) {
                    queue.offer(cur.left);
                }if (cur.right!=null){
                    queue.offer(cur.right);
                }
                size--;
            }
            ret.add(list);
        }
        return ret;
    }
    //是否为完全二叉树
    public boolean isCompleteTree(TreeNode root){
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode cur=queue.poll();
            if (cur==null){
                break;
            }
            queue.offer(cur.left);
            queue.offer(cur.right);
        }
        while (!queue.isEmpty()){
            if ( queue.poll()!=null){
                return false;
            }
        }
        return true;
    }
    //二叉树的最近公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root,TreeNode p,TreeNode q){
        if (root==null){
            return null;
        }
        if (root==p||root==q){
            return root;
        }
        TreeNode leftTree=lowestCommonAncestor(root.left,p,q);
        TreeNode rightTree=lowestCommonAncestor(root.right,p,q);
        if (leftTree!=null&&rightTree!=null){
            return root;
        } else if (leftTree!=null) {
            return leftTree;
        }else {
            return rightTree;
        }
    }
    //法二：
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p,TreeNode q) {
        if (root==null){
            return root;
        }
        //1，获取指定路劲上的节点
        Stack<TreeNode> stackP=new Stack<>();
        getPath(root,p,stackP);
        Stack<TreeNode> stackQ=new Stack<>();
        getPath(root,q,stackQ);
        //2，让两个路径一样长度
        int sizeP=stackP.size();
        int sizeQ=stackQ.size();
        if(sizeP>sizeQ){
            int size=sizeP-sizeQ;
            while (size!=0){
                stackP.pop();
                size--;
            }
        }else {
            int size=sizeQ-sizeP;
            while (size!=0){
                stackQ.pop();
                size--;
            }
        }
        //3，找到两个栈中元素相同的一项
        while (!stackP.isEmpty()&&!stackQ.isEmpty()){
            if (stackP.peek()==stackQ.peek()){
                return stackP.peek();
            }else {
                stackP.pop();
                stackQ.pop();
            }
        }
        return null;

    }
    private boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack){
        if (root==null){
            return false;
        }
        stack.push(root);
        if (root==node) {
            return true;
        }
        boolean flg=getPath(root.left,node,stack);
        if (flg){
            return true;
        }
        boolean flg2=getPath(root.right,node,stack);
        if (flg2){
            return true;
        }
        stack.pop();
        return false;
    }
    //前序遍历（非递归）
    public void preOrder2(TreeNode root){
        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=root;
        while (cur!=null||!stack.isEmpty()){
            while (cur!=null){
                stack.push(cur);
                System.out.print(cur.val+" ");
                cur=cur.left;
            }//先写里面
            TreeNode top=stack.pop();
            cur=top.right;
        }


    }
    //中序遍历（非递归）
    public void midOrder2(TreeNode root){
        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=root;
        while (cur!=null||!stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            System.out.print(top.val + " ");
            cur = top.right;
        }
    }
    //后序遍历（非递归）
    public void postOrder2(TreeNode root){
        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=root;
        TreeNode prev=null;
        while (cur!=null||!stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.peek();
            if (top.right==null||top.right==prev){
                stack.pop();
                System.out.print(top.val + " ");
                prev=top;
            }else {
                cur = top.right;
            }
        }
    }
    //前序与中序遍历来构造二叉树(难)
    public  int preIndex;
    public  TreeNode buildTreePM(char[] proOrder,char [] midOrder){
        return buildTreeChild1(proOrder,midOrder,0,midOrder.length-1);
    }
    private  int finRootIndex1(char [] midOrder,int inBegin,int inEnd,char k){
        for (int i = inBegin; i <= inEnd; i++) {
            if (midOrder[i]==k){
                return i;
            }
        }
        return -1;
    }
    private  TreeNode buildTreeChild1(char[] proOrder,char [] midOrder,int inBegin,int inEnd){
        if (inBegin>inEnd){
            return null;
        }
        TreeNode root=new TreeNode(proOrder[preIndex]);
        int rootIndex=finRootIndex1(midOrder,inBegin,inEnd,proOrder[preIndex]);
        preIndex++;
        root.left=buildTreeChild1(proOrder,midOrder,inBegin,rootIndex-1);
        root.right=buildTreeChild1(proOrder,midOrder,rootIndex+1,inEnd);
        return root;
    }

    //根据中序和后序进行创建一个二叉树
    public int postIndex=0;

    public  TreeNode buildTreeMP(char[] midOrder,char [] postOrder){
        postIndex=postOrder.length-1;
        return buildTreeChild2(midOrder,postOrder,0,midOrder.length-1);
    }
    private  int finRootIndex2(char [] midOrder,int inBegin,int inEnd,char k){
        for (int i = inBegin; i <= inEnd; i++) {
            if (midOrder[i]==k){
                return i;
            }
        }
        return -1;
    }
    private  TreeNode buildTreeChild2(char[] midOrder,char [] postOrder,int inBegin,int inEnd){
        if (inBegin>inEnd){
            return null;
        }
        TreeNode root=new TreeNode(postOrder[preIndex]);
        int rootIndex=finRootIndex2(midOrder,inBegin,inEnd,postOrder[preIndex]);
        preIndex--;
        root.right=buildTreeChild2(midOrder,postOrder,rootIndex+1,inEnd);
        root.left=buildTreeChild2(midOrder,postOrder,inBegin,rootIndex-1);
        return root;
    }
    //根据二叉树创建一个字符串
    //给你一个二叉树的根结点，请你采用前序遍历的方式，将二叉树转换成为一个由括号和字符组成的字符串
    //空节点由一对括号表示，省略没有意义的括号
    //输入【1，2，3，4】输出：1（2（4））（3）
    //输入【1,2，3，null，4】输出：1（2（）（4））（3）
    public String tree2str(TreeNode root){
        StringBuilder stringBuilder=new StringBuilder();
        tree2strChild(root,stringBuilder);
        return stringBuilder.toString();
    }
    private  void tree2strChild(TreeNode root,StringBuilder stringBuilder){
        if (root==null){
            return;
        }
        stringBuilder.append(root.val);
        if (root.left!=null){
            stringBuilder.append("(");
            tree2strChild(root.left,stringBuilder);
            stringBuilder.append(")");
        }else {
            //左边为空，右边也为空
            if (root.right==null){
                return;
            }else {
                stringBuilder.append("()");
            }
        }
        //右树
        if (root.right==null){
            return;
        }else {
            stringBuilder.append("(");
            tree2strChild(root.right,stringBuilder);
            stringBuilder.append(")");
        }

    }
}





public class Test {
    public static void main(String[] args) {
        BinaryTree binaryTree=new BinaryTree();
        BinaryTree.TreeNode root=binaryTree.createTree();
        binaryTree.preOrder(root);
        System.out.println();
        binaryTree.midOrder(root);
        System.out.println();
        binaryTree.postOrder(root);
        System.out.println();
        /*System.out.println();
        System.out.println("节点的个数：");
        System.out.println(binaryTree.size(root));
        binaryTree.size2(root);
        System.out.println(BinaryTree.nodeSize);
        System.out.println("叶子的个数：");
        System.out.println(binaryTree.getLeafNodeCount(root));
        binaryTree.getLeafNodeCount2(root);
        System.out.println(BinaryTree.nodeLeafSize);
        System.out.println("求树的高度");
        System.out.println(binaryTree.getHeight(root));
        System.out.println("查找某个值");
        System.out.println(binaryTree.find(root, 'B').val);
        System.out.println("测试是否为满二叉树");
        System.out.println(binaryTree.isCompleteTree(root));
        binaryTree.preOrder(root);
        System.out.println();
        binaryTree.preOrder2(root);
        System.out.println();
        System.out.println("++++++++++++++++++++++");
        binaryTree.midOrder(root);
        System.out.println();
        binaryTree.midOrder2(root);
        System.out.println();
        System.out.println("+++++++++++++++++++++");
        binaryTree.postOrder(root);
        System.out.println();
        binaryTree.postOrder2(root);
        System.out.println();*/
    }
}
